package listbyorder.access201_300.test210;

import java.util.*;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/22 22:46
 */
public class Solution1 {

    public int[] findOrder(int numCourses, int[][] prerequisites) {

        int[] res = new int[numCourses];
        int index = 0;

        // 保存每一个课程的编号
        HashSet<Integer> set = new HashSet<>();

        // key表示课程key， value表示课程value的先修课程的个数
        HashMap<Integer, Integer> preC = new HashMap<>();

        // key表示成成key， value表示车程key的下一可达的课程集合
        HashMap<Integer, List<Integer>> nextCs = new HashMap<>();

        int len = prerequisites.length;

        for (int i = 0; i < len; i++) {
            int key = prerequisites[i][0];
            int value = prerequisites[i][1];

            set.add(key);
            set.add(value);

            if (!preC.containsKey(key)) {
                preC.put(key, 0);
            }

            if (!preC.containsKey(value)) {
                preC.put(value, 0);
            }

            int num = preC.get(key);
            preC.put(key, num + 1);

            if (!nextCs.containsKey(value)) {
                nextCs.put(value, new ArrayList<Integer>());
            }

            List<Integer> list = nextCs.get(value);
            list.add(key);
        }

        // 创建一个队列
        Queue<Integer> queue = new LinkedList<>();

        for (Integer key : set) {
            if (preC.get(key) == 0) {
                queue.add(key);
                res[index++] = key;
            }
        }

        while (!queue.isEmpty()) {
            int key = queue.poll();
            List<Integer> list = nextCs.getOrDefault(key, new ArrayList<>());

            for (Integer v : list) {
                int num = preC.get(v);
                if (num == 1) {
                    queue.offer(v);
                    res[index++] = v;
                }
                preC.put(v, num - 1);
            }
        }

        for (Integer k : preC.keySet()) {
            if (preC.get(k) != 0) {
                return new int[0];
            }
        }

        int i = 0;
        while (index != numCourses) {
            for (; i < numCourses; i++) {
                if (!set.contains(i)) {
                    res[index++] = i;
                }
            }
        }
        return res;
    }
}
